package LintCode;

import java.util.Collections;

/**
 * @Classname DeleteString
 * @Description TODO
 * @Date 2021/3/6 9:47
 * @Created by ASUS
 * 给定一个字符串，要求去掉一个字符，使得剩下的两个字符串按顺序拼接在一起，
 * 使得最后得到的字符串字典序最小。返回这个字符串。
 * 样例
 * <p>
 * 例 1:
 * <p>
 * 输入:"acd"
 * 输出:"ac"
 * 解释:"ac"是字典序最小的
 * <p>
 * 例 2:
 * <p>
 * 输入:"ozwdtvxuhx"
 * 输出:"owdtvxuhx"
 */
public class DeleteString {
    /**
     * @param str: the str
     * @return: the delete position
     */
    public String deleteString(String str) {
        // Write your code here.
        // 类似于比较整数的大小问题，先看高位的数值
        if (str == null || str.length() < 2) return "";
        int index = -1;
        for (int i = 0; i < str.length() - 1; i++) {
            if (str.charAt(i) > str.charAt(i + 1)) {
                index = i;
                break;
            }
        }
        index = index == -1 ? str.length() - 1 : index;
        return str.substring(0, index) + str.substring(index + 1);
    }

    /**
     * @param str: the string
     * @param k:   the length
     * @return: the substring with  the smallest lexicographic order
     */
    public String deleteChar(String str, int k) {
        // Write your code here.
        int index = -1;
        for (int i = 0; i < str.length() && str.length() > k; i++) {
            if (i == str.length() - 1) str = str.substring(0, i);
            else if (str.charAt(i) > str.charAt(i + 1)) {
                str = str.substring(0, i) + str.substring(i + 1);
                i = -1;
            }
        }
        return str;
    }

    public static void main(String[] args) {
        System.out.println(new DeleteString().deleteString("vowdtvxuhx"));
        System.out.println(new DeleteString().deleteChar("fskacsbi", 2));
    }
}
